Aufgabe 3.2.6.: Sei A = (Q, Σ, δ, q_{0}, q_{f}) ein ε-NEA, derart dass es keine zu q_{0} hinführenden und keine von q_{f} ausgehenden Übergänge gibt. Beschreiben Sie für jede der folgenden Modifikationen von A die akzeptierte Sprache als Modifikation von L = L(A):

a) Der Automat, der aus A konstruiert wird, indem ein ε-Übergang von q_{f} nach q_{0} hinzugefügt wird.

b) Der Automat, der aus A konstruiert wird, indem ε-Übergänge von q_{0} zu jedem Zustand, der von q_{0} erreichbar ist, auf einem Pfad, dessen Beschriftung Zeichen aus Σ sowie ε enthalten können

c) Der Automat, der aus A konstruiert wird, in dem ε-Übergänge von jedem Zustand zu q_{f} hinzugefügt werden, von denen aus q_{f} auf irgendeinem Pfad erreichbar ist.

d) Der Automat, der aus A konstruiert wird, indem die unter b) und c) geforderte Modifikationen ausgeführt werden.

Lösung:

a) Sei A_{mod} der modifizierte, aus A konstruierte ε-NEA. Wird ε-Übergang von q_{f} nach q_{0} hinzugefügt, dann muss der Automat mindestens einmal Zustand q_{f} erreichen, damit er akzeptiert. Ist er einmal in q_{f} kann er durch den hinzugefügten ε-Übergang "annehmen" die Zeichenreihe sei noch nicht beendet, und erwarten, dass noch einmal die zu q_{f} führende Zeichenreihe folgt. Ist q_{f} erreicht, wiederholt sich dieses Schema jedesmal, wenn eine zu q_{f} führende Zeichenreihe eingegeben wurde. Das bedeutet:

L(A_{mod}) = L(A)L(A)^{∗}  (1)

b) Der Automat A sehe wie folgt aus.

0  a_{1}  1  a_{2}  2  a_{3}  …  a_{n}  n

Dieser Automat akzeptiert alle Zeichenreihen, die die Form a_{1}a_{2}a_{3}...a_{n} haben. Fügt man jetzt ε-Übergänge hinzu, von q_{0} zu jedem Zustand, der von q_{0} erreichbar ist, dann sieht der Automat A_{mod} wie folgt aus:

0  1  2  n a_{1}  a_{2}  a_{3}  …  a_{n} ε  ε  ε  ε  ε

Dieser Automat akzeptiert alle Zeichenreihen, die folgender Form sind: 1) a_{1}a_{2}a_{3}...a_{n}

2) a_{2}a_{3}...a_{n}

3) a_{3}...a_{n} ...

n) a_{n} n+1) ε Die Sprache L(A_{mod}) ist demnach die Menge aller Suffixe von den Elementen in L(A).

c) Der Automat A sehe wie folgt aus.

0  a_{1}  1  a_{2}  2  a_{3}  …  a_{n}  n

Dieser Automat akzeptiert alle Zeichenreihen, die die Form a_{1}a_{2}a_{3}...a_{n} haben. Fügt man jetzt ε-Übergänge hinzu, von jedem q_{i} zu q_{f}, q_{f} von q_{i} aus auf irgendeinem Pfad erreichbar ist, dann sieht der modifizierte Automat A_{mod} wie folgt aus:

0  1  2  n a_{1}  a_{2}  a_{3}  …  a_{n} ε  ε  ε  ε  ε

Dieser Automat akzeptiert alle Zeichenreihen, die folgender Form sind: 1) a_{1}a_{2}a_{3}...a_{n−1}

2) a_{1}a_{2}a_{3}...a_{n−2}

3) a_{1}a_{2}a_{3}...a_{n−3}

... n-1) a_{1}a_{2}

n) a_{1} n+1) ε Die Sprache L(A_{mod}) ist demnach die Menge aller Prefixe von den Elementen in L(A).

d) Der Automat A sehe wie folgt aus.

0  a_{1}  1  a_{2}  2  a_{3}  …  a_{n}  n

Dieser Automat akzeptiert alle Zeichenreihen, die die Form a_{1}a_{2}a_{3}...a_{n} haben. Fügt man jetzt ε-Übergänge hinzu, von jedem q_{i} zu q_{f}, q_{f} von q_{i} aus auf irgendeinem Pfad erreichbar ist, dann sieht der modifizierte Automat A_{mod} wie folgt aus:

0  1  2  n a_{1}  a_{2}  a_{3}  …  a_{n} ε  ε  ε  ε  εε  ε  ε  ε  ε

Die Sprache L(A_{mod}) dieses Automaten akzeptiert alle Zeichenreihen, die Teilzeichenreihen von Elementen in L(A).